package com.chl.chart;

import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;

import java.util.*;

public class RemoveCycleEdge {

	static class Edge {
        String source;
        String target;
        int value;
        JSONObject json;

        Edge(String source, String target, int value, JSONObject json) {
            this.source = source;
            this.target = target;
            this.value = value;
            this.json = json;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Edge)) return false;
            Edge edge = (Edge) o;
            return Objects.equals(source, edge.source) &&
                   Objects.equals(target, edge.target);
        }

        @Override
        public int hashCode() {
            return Objects.hash(source, target);
        }

        @Override
        public String toString() {
            return source + "->" + target + "(value=" + value + ")";
        }
    }

    // ==================== 结果类 ====================
    private static class CycleResult {
        boolean hasCycle;
        Edge minCycleEdge;
        List<String> cyclePath;
        Set<Edge> cycleEdges;

        CycleResult(boolean hasCycle, Edge minCycleEdge, List<String> cyclePath, Set<Edge> cycleEdges) {
            this.hasCycle = hasCycle;
            this.minCycleEdge = minCycleEdge;
            this.cyclePath = cyclePath != null ? new ArrayList<>(cyclePath) : Collections.emptyList();
            this.cycleEdges = cycleEdges != null ? new HashSet<>(cycleEdges) : Collections.emptySet();
        }
    }

    // ==================== 异常类：用于跳出 DFS 并携带环信息 ====================
    private static class CycleFoundException extends RuntimeException {
        List<String> cyclePath;
        Set<Edge> cycleEdges;

        CycleFoundException(List<String> cyclePath, Set<Edge> cycleEdges) {
            this.cyclePath = cyclePath;
            this.cycleEdges = cycleEdges;
        }
    }

    /**
     * 主方法：循环移除所有环，并输出每个环的路径
     */
    public JSONArray removeAllCycles(JSONArray links) {
        int iteration = 0;

        while (true) {
            iteration++;
            System.out.println("\n--- 第 " + iteration + " 轮检测 ---");

            CycleDetector detector = new CycleDetector();
            CycleResult result = detectCycleWithException(detector, links);

            if (!result.hasCycle) {
                System.out.println("✅ 无环，处理结束。");
                break;
            }

            // 输出环路径
            System.out.println("发现环路径: " + String.join(" -> ", result.cyclePath));

            // 找出环中 value 最小的边
            Edge minEdge = Collections.min(result.cycleEdges, Comparator.comparingInt(e -> e.value));
            System.out.println("移除边: " + minEdge);

            // 从 links 中移除该边
            JSONArray newLinks = new JSONArray();
            for (Object obj : links) {
                JSONObject json = (JSONObject) obj;
                Edge e = new Edge(
                    json.getString("source"),
                    json.getString("target"),
                    json.getIntValue("value"),
                    json
                );
                if (!e.equals(minEdge)) {
                    newLinks.add(json);
                }
            }
            links = newLinks;
            System.out.println("剩余边数: " + links.size());
        }

        System.out.println("\n✅ 所有环已清除，共处理 " + iteration + " 轮");
        return links;
    }

    /**
     * 调用检测器，并捕获异常获取环信息
     */
    private CycleResult detectCycleWithException(CycleDetector detector, JSONArray links) {
        try {
            // 正常返回无环
            detector.detectCycle(links);
            return new CycleResult(false, null, null, null);
        } catch (CycleFoundException e) {
            Edge minEdge = Collections.min(e.cycleEdges, Comparator.comparingInt(edge -> edge.value));
            return new CycleResult(true, minEdge, e.cyclePath, e.cycleEdges);
        }
    }

    // ==================== 环检测器（带路径追踪） ====================

    private static class CycleDetector {
        private Map<String, List<Edge>> graph = new HashMap<>();
        private Map<String, Integer> visited = new HashMap<>();
        private Deque<String> pathStack = new LinkedList<>();
        private Map<String, Edge> edgeFrom = new HashMap<>();

        public void detectCycle(JSONArray links) {
            buildGraph(links);
            visited.clear();
            pathStack.clear();
            edgeFrom.clear();

            for (String node : graph.keySet()) {
                if (visited.getOrDefault(node, 0) == 0) {
                    dfs(node);
                }
            }
        }

        private boolean dfs(String node) {
            visited.put(node, 1);
            pathStack.push(node);

            for (Edge edge : graph.getOrDefault(node, Collections.emptyList())) {
                String neighbor = edge.target;

                if (visited.getOrDefault(neighbor, 0) == 0) {
                    edgeFrom.put(neighbor, edge);
                    if (dfs(neighbor)) {
                        return true;
                    }
                } else if (visited.getOrDefault(neighbor, 0) == 1) {
                    // 发现环！提取路径
                    List<String> cyclePath = new ArrayList<>();
                    boolean startAdding = false;
                    List<String> stackList = new ArrayList<>(pathStack);
                    Collections.reverse(stackList); // 栈顶在最后

                    for (String n : stackList) {
                        if (n.equals(neighbor)) {
                            startAdding = true;
                        }
                        if (startAdding) {
                            cyclePath.add(n);
                        }
                    }
                    cyclePath.add(neighbor); // 闭合

                    Set<Edge> cycleEdges = new LinkedHashSet<>();
                    for (int i = 0; i < cyclePath.size() - 1; i++) {
                        String from = cyclePath.get(i);
                        String to = cyclePath.get(i + 1);
                        for (Edge e : graph.getOrDefault(from, Collections.emptyList())) {
                            if (e.target.equals(to)) {
                                cycleEdges.add(e);
                                break;
                            }
                        }
                    }

                    throw new CycleFoundException(cyclePath, cycleEdges);
                }
            }

            visited.put(node, 2);
            pathStack.pop();
            return false;
        }

        private void buildGraph(JSONArray links) {
            graph.clear();
            for (Object obj : links) {
                JSONObject json = (JSONObject) obj;
                String source = json.getString("source");
                String target = json.getString("target");
                int value = json.getIntValue("value");

                Edge edge = new Edge(source, target, value, json);
                graph.computeIfAbsent(source, k -> new ArrayList<>()).add(edge);
                graph.putIfAbsent(target, new ArrayList<>());
            }
        }
    }

    // ==================== 测试用例 ====================

    public static void main(String[] args) {
        JSONArray links = new JSONArray();

        addLink(links, "A", "B", 5);
        addLink(links, "B", "C", 3);
        addLink(links, "C", "A", 2);

        addLink(links, "D", "E", 4);
        addLink(links, "E", "F", 1);
        addLink(links, "F", "D", 6);

        addLink(links, "C", "D", 7);

        System.out.println("原始 links: " + links);

        RemoveCycleEdge remover = new RemoveCycleEdge();
        JSONArray cleaned = remover.removeAllCycles(links);

        System.out.println("\n最终无环图: " + cleaned);
    }

    private static void addLink(JSONArray links, String source, String target, int value) {
        JSONObject obj = new JSONObject();
        obj.put("source", source);
        obj.put("target", target);
        obj.put("value", value);
        links.add(obj);
    }
}
